
import java.util.Arrays;

/**
 * 快速排序
 * <p>
 * 快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，
 * 我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
 * 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，
 * 将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，
 * 数组 p 到 r 之间的数据就被分成了三个部分，
 * 前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，
 * 后面的 q+1 到 r 之间是大于 pivot 的
 * 根据分治、递归的处理思想，
 * 我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，
 * 直到区间缩小为 1，就说明所有的数据都有序了。
 * <p>
 * 如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，
 * 那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是 O(nlogn)。
 * 但是，公式成立的前提是每次分区操作，我们选择的 pivot 都很合适，
 * 正好能将大区间对等地一分为二。但实际上这种情况是很难实现的。
 * 我举一个比较极端的例子。如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，
 * 那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，
 * 才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，
 * 这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。
 * T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。
 * 而且，我们也有很多方法将这个概率降到很低，
 * <p>
 * 快速排序通过设计巧妙的原地分区函数，可以实现原地排序，
 * 解决了归并排序占用太多内存的问题。
 * <p>
 * 因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，
 * 在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。
 *
 * @author gaoge
 * @since 2022/11/29 17:07
 */
public class QuickSort {


    /**
     * 快速排序算法
     *
     * @param a 是数组
     * @param n 表示数组大小
     */
    public static void quickSort(int[] a, int n) {
        quickSortInternally(a, 0, n - 1);
    }

    /**
     * 递归调用函数
     *
     * @param a 数组
     * @param p 开始索引
     * @param r 结束索引
     */
    private static void quickSortInternally(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }
        // 获取分区点
        int q = partition(a, p, r);
        quickSortInternally(a, p, q - 1);
        quickSortInternally(a, q + 1, r);
    }

    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];
        int i = p;
        for (int j = p; j < r; ++j) {
            if (a[j] < pivot) {
                if (i == j) {
                    ++i;
                } else {
                    int tmp = a[i];
                    a[i++] = a[j];
                    a[j] = tmp;
                }
            }
        }

        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;
        return i;
    }

    public static void main(String[] args) {
        int[] ints = new int[]{9, 8, 4, 6, 7, 7, 5, 4, 0, 3, 34, 12};
        System.out.println(Arrays.toString(ints));
        quickSort(ints, ints.length);
        System.out.println(Arrays.toString(ints));
    }
}
